1. Field of the Invention
The present invention relates generally to a method and apparatus for implementing a packet switch protocol for a data communication switching network. More particulary, the present invention relates to a method and apparatus for implementing a handshaking protocol for which computational speed is independent of signal propogation delays between a sending node and a receiving node. In a switching network which uses this protocol the rate of data transmission between the sending and receiving nodes is not affected by the signal propagation delay between the sender and the receiver.
2. Description of the Prior Art
Many data processing applications exist in which computational speed is a limiting factor in the time needed to complete the application. Using larger and faster single processor systems for these applications provides only a limited benefit since, even though these machines may perform the individual calculations at a higher rate, they still process the instructions and data serially. One approach to meeting the need for computational speed is parallel processing.
For this processing method, an application is divided into parts which are suitably distributed among numerous processors operating concurrently. The success of a parallel processing system depends heavily on the communication among the processors and memory used in the system. In a parallel processing environment, processors communicate with each other, as well as with memory, to fetch instructions and operands, store intermediate results, handle interrupts, pass messages and handle input and output functions.
This communication function is often implemented by one or more switching networks coupling the various procesors and memory subsystems together. For effective performance in a parallel processing environment, it is desirable for these switching networks to provide efficient and effective information transmission among the processors and memory subsystems via the workings of their interface logic and control protocols. A key factor in the design of such communications networks is the signal propagation delay for data being transferred between terminal nodes (i.e. processors or memory subsystems) on the network. The practical issues of complexity and cost should also be considered while attempting to optimize the performance of a network.
In the prior art, U.S. Pat. No. 4,412,285 to P. M. Neches et al. relates to a communication mechanism for use among multiple processors and peripheral devices. This communications system transfers data among the terminal nodes (i.e. processors or peripheral devices) via hierarchically coupled switching nodes according to a fixed priority scheme. In this system, transmission line delays between switching nodes are described as being constant and substantially identical. A change in the transmission delay between nodes results in a change in the rate at which data may be transferred through the network. This renders the operating speed of the network dependent upon the signal propagation delay in the switching network.
U.S. Pat. No. 4,276,656 to E. M. Petryk Jr. relates to a communications network in which data is transformed from multi-bit words to a bit-serial signal, and then converted for transmission over an optical fiber link. The use of a bit-serial signal and conversion needed to use the optical fiber links may increase the cost and the signal propagation delay of the system relative to a switching network which uses a parallel-bit signal and conventional electrical transmission lines.
U.S. Pat. No. 4,494,230 to J. S. Turner relates to a data communications switching system which uses a bidirectional bit-serial data transmission link and, in which, control signaling to the various nodes of the system uses the same serial link that is used to transfer data. This technique may require a delay between messages to change the data routing performed by the switch. A delay of this type is added onto the signal propagation delay through the network.
A section of a textbook by A. S. Tanenbaum; entitled Computer Networks, Prentice Hall, 1981, pp. 153-157; relates to a data transmission system which uses a pipelining protocol to mitigate a loss in efficiency of the system resulting from relatively long signal propagation delays. This protocol includes provisions for positive or negative acknowledgement from the receiving node, provisions for assuming an error condition after a prescribed amount of time has elapsed without an acknowledgement, and a sliding window mechanism for buffering data within the sending and receiving units.